package com.clps.algorithm03.队列;

/**
 * 队列常用的两种实现方式,一种是使用链表,一种是使用数组,使用单向链表实现对垒不会出现溢出的问题,队列的长度也没有限制,但是删除的时间代价比价高
 * 所以我们一般使用双向链表,所以我们一般使用双向链表,使用两个指针,一个指针指向队列的头,一个指向队列的尾,删除的时候只能能删除(head)节点,添加的时候只能在尾部添加,如下图所示.
 * @param <E>
 */
public class Queue<E> {

   private  QueueNode<E> head;
   private  QueueNode<E> tail;
   private  int size;//队列中的元素的个数


    public  void  add(E val){
        if(isEmpty()){
            head = new QueueNode<>(val,null,null);
            tail = head;
        }else{//如果不为空就添加尾数
            tail = new QueueNode<>(val,tail,null);
            tail.pre.next  = tail;
        }
        size++;
    }


    //删除队列中的元素
    public  E remove() {
        if (isEmpty()) {
            throw new NullPointerException("队列为空");
        }
            E res = head.val;
            if (size() == 1) { //只有一个节点,全部删除
                head = null;
                tail = null;
            } else {
                QueueNode headNext = head.next;
                headNext = null;
                headNext.pre = null;
                head = headNext;
            }
            size--;
            return res;
        }



    private int size() {
        return size;
    }

    private boolean isEmpty() {
        return  size ==0;
    }

}

class QueueNode<E>{
    E val;//节点值
    QueueNode pre; //指向前一个节点
    QueueNode next; //指向后一个节点


    public QueueNode(E val, QueueNode pre, QueueNode next) {
        this.val = val;
        this.pre = pre;
        this.next = next;
    }



}
